选择排序

从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。

选择排序需要 ~N²/2 次比较和 ~N 次交换，它的运行时间与输入无关，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。

public class Selection<T extends Comparable<T>> extends Sort<T> {
    @Override
    public void sort(T[] nums) {
        int N = nums.length;
        for (int i = 0; i < N - 1; i++) {
            int min = i;
            for (int j = i + 1; j < N; j++) {
                if (less(nums[j], nums[min])) {
                    min = j;
                }
            }
            swap(nums, i, min);
        }
    }
}

冒泡排序

从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。

在一轮循环中，如果没有发生交换，那么说明数组已经是有序的，此时可以直接退出。

public class Bubble<T extends Comparable<T>> extends Sort<T> {
    @Override
    public void sort(T[] nums) {
        int N = nums.length;
        boolean isSorted = false;
        for (int i = N - 1; i > 0 && !isSorted; i--) {
            isSorted = true;
            for (int j = 0; j < i; j++) {
                if (less(nums[j + 1], nums[j])) {
                    isSorted = false;
                    swap(nums, j, j + 1);
                }
            }
        }
    }
}

插入排序

每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。

对于数组 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交换相邻元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量。

插入排序的时间复杂度取决于数组的初始顺序，如果数组已经部分有序了，那么逆序较少，需要的交换次数也就较少，时间复杂度较低。

平均情况下插入排序需要 ~N²/4 比较以及 ~N²/4 次交换；
最坏的情况下需要 ~N²/2 比较以及 ~N²/2 次交换，最坏的情况是数组是倒序的；
最好的情况下需要 N-1 次比较和 0 次交换，最好的情况就是数组已经有序了。

public class Insertion<T extends Comparable<T>> extends Sort<T> {
    @Override
    public void sort(T[] nums) {
        int N = nums.length;
        for (int i = 1; i < N; i++) {
            for (int j = i; j > 0 && less(nums[j], nums[j - 1]); j--) {
                swap(nums, j, j - 1);
            }
        }
    }
}

希尔排序

对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少 1。希尔排序的出现就是为了解决插入排序的这种局限性，它通过交换不相邻的元素，每次可以将逆序数量减少大于 1。

希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的。

public class Shell<T extends Comparable<T>> extends Sort<T> {
    @Override
    public void sort(T[] nums) {
        int N = nums.length;
        int h = 1;
        while (h < N / 3) {
            h = 3 * h + 1; // 1, 4, 13, 40, ...
        }
        while (h >= 1) {
            for (int i = h; i < N; i++) {
                for (int j = i; j >= h && less(nums[j], nums[j - h]); j -= h) {
                    swap(nums, j, j - h);
                }
            }
            h = h / 3;
        }
    }
}

希尔排序的运行时间达不到平方级别，使用递增序列 1, 4, 13, 40, … 的希尔排序所需要的比较次数不会超过 N 的若干倍乘于递增序列的长度。后面介绍的高级排序算法只会比希尔排序快两倍左右。

归并排序

归并排序的思想是将数组分成两部分，分别进行排序，然后归并起来。

归并方法将数组中两个已经排序的部分归并成一个。

private static void merge(int[] arr,int left,int mid,int right,int[] temp){
    int i = left;//左序列指针
    int j = mid+1;//右序列指针
    int t = 0;//临时数组指针
    while (i<=mid && j<=right){
        if(arr[i]<=arr[j]){
            temp[t++] = arr[i++];
        }else {
            temp[t++] = arr[j++];
        }
    }
    while(i<=mid){//将左边剩余元素填充进temp中
        temp[t++] = arr[i++];
    }
    while(j<=right){//将右序列剩余元素填充进temp中
        temp[t++] = arr[j++];
    }
    t = 0;
    //将temp中的元素全部拷贝到原数组中
    while(left <= right){
        arr[left++] = temp[t++];
    }
}

import java.util.Arrays;
public class MergeSort {
    public static void main(String []args){
        int []arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int []arr){
        int []temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        sort(arr,0,arr.length-1,temp);
    }
    private static void sort(int[] arr,int left,int right,int []temp){
        if(left<right){
            int mid = (left+right)/2;
            sort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
            sort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
            merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
        }
    }
}

快速排序

https://www.cnblogs.com/chengxiao/p/6262208.html

1. 基本算法

归并排序将数组分为两个子数组分别排序，并将有序的子数组归并使得整个数组排序；
快速排序通过一个切分元素将数组分为两个子数组，左子数组小于等于切分元素，右子数组大于等于切分元素，将这两个子数组排序也就将整个数组排序了。

public class QuickSort<T extends Comparable<T>> extends Sort<T> {
    @Override
    public void sort(T[] nums) {
        sort(nums, 0, nums.length - 1);
    }
    private void sort(T[] nums, int l, int h) {
        if (h <= l)
            return;
        int j = partition(nums, l, h);
        sort(nums, l, j - 1);
        sort(nums, j + 1, h);
    }
}

2. 切分

取 a[l] 作为切分元素，然后从数组的左端向右扫描直到找到第一个大于等于它的元素，再从数组的右端向左扫描找到第一个小于它的元素，交换这两个元素。不断进行这个过程，就可以保证左指针 i 的左侧元素都不大于切分元素，右指针 j 的右侧元素都不小于切分元素。当两个指针相遇时，将切分元素 a[l] 和 a[j] 交换位置。

private int partition(T[] nums, int l, int h) {
    int i = l, j = h + 1;
    T v = nums[l];
    while (true) {
        while (less(nums[++i], v) && i != h) ;
        while (less(v, nums[--j]) && j != l) ;
        if (i >= j)
            break;
        swap(nums, i, j);
    }
    swap(nums, l, j);
    return j;
}

3. 性能分析

快速排序是原地排序，不需要辅助数组，但是递归调用需要辅助栈。

快速排序最好的情况下是每次都正好将数组对半分，这样递归调用次数才是最少的。这种情况下比较次数为 C_N=2C_N/2+N，复杂度为 O(NlogN)。

最坏的情况下，第一次从最小的元素切分，第二次从第二小的元素切分，如此这般。因此最坏的情况下需要比较 N²/2。为了防止数组最开始就是有序的，在进行快速排序时需要随机打乱数组。

4. 算法改进

4.1 切换到插入排序

因为快速排序在小数组中也会递归调用自己，对于小数组，插入排序比快速排序的性能更好，因此在小数组中可以切换到插入排序。

4.2 三数取中

最好的情况下是每次都能取数组的中位数作为切分元素，但是计算中位数的代价很高。一种折中方法是取 3 个元素，并将大小居中的元素作为切分元素。

https://www.cnblogs.com/chengxiao/p/6262208.html

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("排序结果：" + Arrays.toString(arr));
    }

    /**
     * @param arr
     * @param left  左指针
     * @param right 右指针
     */
    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            //获取枢纽值，并将其放在当前待处理序列末尾
            dealPivot(arr, left, right);
            //枢纽值被放在序列末尾
            int pivot = right - 1;
            //左指针
            int i = left;
            //右指针
            int j = right - 1;
            while (true) {
                while (arr[++i] < arr[pivot]) {
                }
                while (j > left && arr[--j] > arr[pivot]) {
                }
                if (i < j) {
                    swap(arr, i, j);
                } else {
                    break;
                }
            }
            if (i < right) {
                swap(arr, i, right - 1);
            }
            quickSort(arr, left, i - 1);
            quickSort(arr, i + 1, right);
        }

    }

    /**
     * 处理枢纽值
     *
     * @param arr
     * @param left
     * @param right
     */
    public static void dealPivot(int[] arr, int left, int right) {
        int mid = (left + right) / 2;
        if (arr[left] > arr[mid]) {
            swap(arr, left, mid);
        }
        if (arr[left] > arr[right]) {
            swap(arr, left, right);
        }
        if (arr[right] < arr[mid]) {
            swap(arr, right, mid);
        }
        swap(arr, right - 1, mid);
    }
}

4.3 三向切分

对于有大量重复元素的数组，可以将数组切分为三部分，分别对应小于、等于和大于切分元素。

三向切分快速排序对于有大量重复元素的随机数组可以在线性时间内完成排序。

public class ThreeWayQuickSort<T extends Comparable<T>> extends QuickSort<T> {

    @Override
    protected void sort(T[] nums, int l, int h) {
        if (h <= l) {
            return;
        }
        int lt = l, i = l + 1, gt = h;
        T v = nums[l];
        while (i <= gt) {
            int cmp = nums[i].compareTo(v);
            if (cmp < 0) {
                swap(nums, lt++, i++);
            } else if (cmp > 0) {
                swap(nums, i, gt--);
            } else {
                i++;
            }
        }
        sort(nums, l, lt - 1);
        sort(nums, gt + 1, h);
    }
}

快速选择

快选 = 快排 + 二分查找

快速排序的 partition() 方法，会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j]，且 a[j+1..h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。

可以利用这个特性找出数组的第 k 个元素。

该算法是线性级别的，假设每次能将数组二分，那么比较的总次数为 (N+N/2+N/4+..)，直到找到第 k 个元素，这个和显然小于 2N

Quick select的average case时间复杂度为O(n)，然而其worst case时间复杂度为O(n^2)

public T select(T[] nums, int k) {
    int l = 0, h = nums.length - 1;
    while (h > l) {
        int j = partition(nums, l, h);
        if (j == k) {
            return nums[k];
        } else if (j > k) {
            h = j - 1;
        } else {
            l = j + 1;
        }
    }
    return nums[k];
}

堆排序

1. 堆

堆中某个节点的值总是大于等于其子节点的值，并且堆是一颗完全二叉树。

堆可以用数组来表示，这是因为堆是完全二叉树，而完全二叉树很容易就存储在数组中。位置 k 的节点的父节点位置为 k/2，而它的两个子节点的位置分别为 2k 和 2k+1。这里不使用数组索引为 0 的位置，是为了更清晰地描述节点的位置关系。

public class Heap<T extends Comparable<T>> {

    private T[] heap;
    private int N = 0;

    public Heap(int maxN) {
        this.heap = (T[]) new Comparable[maxN + 1];
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    private boolean less(int i, int j) {
        return heap[i].compareTo(heap[j]) < 0;
    }

    private void swap(int i, int j) {
        T t = heap[i];
        heap[i] = heap[j];
        heap[j] = t;
    }
}

2. 上浮和下沉

在堆中，当一个节点比父节点大，那么需要交换这个两个节点。交换后还可能比它新的父节点大，因此需要不断地进行比较和交换操作，把这种操作称为上浮。

private void swim(int k) {
    while (k > 1 && less(k / 2, k)) {
        swap(k / 2, k);
        k = k / 2;
    }
}

类似地，当一个节点比子节点来得小，也需要不断地向下进行比较和交换操作，把这种操作称为下沉。一个节点如果有两个子节点，应当与两个子节点中最大那个节点进行交换。

private void sink(int k) {
    while (2 * k <= N) {
        int j = 2 * k;
        if (j < N && less(j, j + 1))
            j++;
        if (!less(k, j))
            break;
        swap(k, j);
        k = j;
    }
}

3. 插入元素

将新元素放到数组末尾，然后上浮到合适的位置。

public void insert(Comparable v) {
    heap[++N] = v;
    swim(N);
}

4. 删除最大元素

从数组顶端删除最大的元素，并将数组的最后一个元素放到顶端，并让这个元素下沉到合适的位置。

public T delMax() {
    T max = heap[1];
    swap(1, N--);
    heap[N + 1] = null;
    sink(1);
    return max;
}

5. 堆排序

把最大元素和当前堆中数组的最后一个元素交换位置，并且不删除它，那么就可以得到一个从尾到头的递减序列，从正向来看就是一个递增序列，这就是堆排序。

5.1 构建堆

无序数组建立堆最直接的方法是从左到右遍历数组进行上浮操作。一个更高效的方法是从右至左进行下沉操作，如果一个节点的两个节点都已经是堆有序，那么进行下沉操作可以使得这个节点为根节点的堆有序。叶子节点不需要进行下沉操作，可以忽略叶子节点的元素，因此只需要遍历一半的元素即可。

5.2 交换堆顶元素与最后一个元素

交换之后需要进行下沉操作维持堆的有序状态。

public class HeapSort<T extends Comparable<T>> extends Sort<T> {
    /**
     * 数组第 0 个位置不能有元素
     */
    @Override
    public void sort(T[] nums) {
        int N = nums.length - 1;
        for (int k = N / 2; k >= 1; k--)
            sink(nums, k, N);

        while (N > 1) {
            swap(nums, 1, N--);
            sink(nums, 1, N);
        }
    }
    private void sink(T[] nums, int k, int N) {
        while (2 * k <= N) {
            int j = 2 * k;
            if (j < N && less(nums, j, j + 1))
                j++;
            if (!less(nums, k, j))
                break;
            swap(nums, k, j);
            k = j;
        }
    }
    private boolean less(T[] nums, int i, int j) {
        return nums[i].compareTo(nums[j]) < 0;
    }
}

6. 分析

一个堆的高度为 logN，因此在堆中插入元素和删除最大元素的复杂度都为 logN。

对于堆排序，由于要对 N 个节点进行下沉操作，因此复杂度为 NlogN。

堆排序是一种原地排序，没有利用额外的空间。

现代操作系统很少使用堆排序，因为它无法利用局部性原理进行缓存，也就是数组元素很少和相邻的元素进行比较和交换。

小结

1. 排序算法的比较

算法	稳定性	时间复杂度	空间复杂度	备注
选择排序	×	N²	1
冒泡排序	√	N ~ N²	1
插入排序	√	N ~ N²	1	时间复杂度和初始顺序有关
希尔排序	×	N^1.3	1	改进版插入排序
快速排序	×	NlogN~ N²	logN
三向切分快速排序	×	N ~ NlogN	logN	适用于有大量重复主键
归并排序	√	NlogN	N
堆排序	×	NlogN	1	无法利用局部性原理

快速排序是最快的通用排序算法，它的内循环的指令很少，而且它还能利用缓存，因为它总是顺序地访问数据。它的运行时间近似为 ~cNlogN，这里的 c 比其它线性对数级别的排序算法都要小。

使用三向切分快速排序，实际应用中可能出现的某些分布的输入能够达到线性级别，而其它排序算法仍然需要线性对数时间。

2. Java 的排序算法实现

Java 主要排序方法为 java.util.Arrays.sort()，对于原始数据类型使用三向切分的快速排序，对于引用类型使用归并排序。

Top K 问题

https://xiaozhuanlan.com/topic/4176082593

快速选择解决

堆排序解决

使用大顶堆来维护最小堆，而不能直接创建一个小顶堆并设置一个大小，企图让小顶堆中的元素都是最小元素

寻找最大top k，使用小顶堆，堆顶元素是当前第 k 大元素，是当前top k 的边界，可以用来判断下一个元素是否需要加入堆，那么加入堆的操作非常少时间复杂度为 O(n)

若寻找最大top k，使用大顶堆，堆顶元素不是边界，每一个元素都需加入堆，然后维护堆的大小，复杂度为O(logk * n)

时间复杂复分析

https://blog.csdn.net/so_geili/article/details/53444816#3

迭代法
Master 定理
1. 公式
2. 比较大小
3. 相等/ 大于 / 小于

刷题技巧

利用utils 暴力做
搜索leetcode
简单方法
复杂方法
debug思路
1. 边界
2. 正负值
3. 特殊情况

数据结构

二叉树

满二叉树

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树

完全二叉树

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树

二叉查找树/二叉排序树

https://www.cnblogs.com/yangecnu/p/Introduce-Binary-Search-Tree.html

二叉查找树的概念定义：（递归概念）

左子树上节点的值均小于根节点的值
右子树上节点的值均大于根节点的值
左右子树也是二叉查找树（递归定义）
树中不存在键值相等的节点

查找操作：递归定义

查找时间复杂度：平衡 logN，最差：树退化成list，N

插入操作：查找对应节点，若存在更新，不存在插入新节点

删除：调整

二叉查找树的最大值最小值：

最大值：最右节点
最小值：最左节点

平衡二叉树

其中两款具有代表性的平衡树分别为AVL树和红黑树。AVL树由于实现比较复杂，而且插入和删除性能差，在实际环境下的应用不如红黑树

AVL树

定义：

一棵空树或左个子树的高度差的绝对值不超过1
左右两个子树都是一棵平衡二叉树（递归定义）

左旋右旋

特点：

实现比较复杂
插入和删除性能差
在实际环境下的应用不如红黑树（接近平衡）
真正的平衡二叉树
在logN时间内做查找插入删除（logN的常量比红黑树的大）

红黑树

http://dandanlove.com/2018/03/18/red-black-tree/

https://juejin.im/post/5a27c6946fb9a04509096248#comment

5个特性（根节点，普通节点，叶子节点，路径红色，路径黑色），三种手段（变色，左旋，右旋），2个结果（接近平衡，logN），应用

本质：一种自平衡(接近平衡)的二叉查找树

动机： AVL树较为严格完全平衡，代价大，红黑树近似平衡，插入查找删除代价小；解决二叉查找树退化为线性的情况，只需要近似平衡就能取得较好的查找效果

规则：这些规则保持了红黑树的自平衡，插入删除元素时需要维持规则

节点是红色或黑色。
根节点是黑色。
每个叶子节点都是黑色的空节点。
每个红色节点的两个子节点都是黑色 / 从每个叶子到根的所有路径上不能有两个连续的红色节点
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

平衡性：

红黑树从根节点到叶子的最长路径不会超过最短路径的2倍
在 O(logn)时间内做查找，插入和删除

调整方式： 有三中方式，组合起来维护红黑树的五个特点

变色
左旋
右旋

应用：

Linux内核中的完全公平调度器、高精度计时器、ext3文件系统等等
Java的TreeMap和TreeSet
C++ STL的map、multimap、multiset

B树

https://yq.aliyun.com/articles/38345

https://blog.csdn.net/aqzwss/article/details/53074186

https://blog.csdn.net/bigtree_3721/article/details/73632405

核心思想：通过多路查找树降低树高，降低查找复杂度

节点结构：假设 M=3 也即最大路数为3

Class Node{
  　int keynum； //结点中当前拥有的关键字的个数，keynum<<Max
  　KeyType key[M+1]； //关键字向量为key[1..keynum]，key[0]不用。
  　Node parent； //指向双亲结点
  　Node son[M+1]；//指向孩子结点的指针数组，孩子指针向量为son[0..keynum]
 }BTreeNode；

B树的特点:

B树是一种多路搜索树
节点上 至多有M-1个关键字(1. 包含具体信息 2. 关键字数组index=0不使用)
每个父节点的孩子数在 [M/2,M] 之间；根节点的孩子数在[2,M] 之间
所有叶子结点位于同一层（因此插入元素时，当前叶子节点存不下后，进行分裂而不是向下增加一层） 自动层次控制
非叶子结点的关键字个数=指向儿子的指针个数-1
树高：$log_M (N+1)/2$ M路，N个关键字
其搜索性能等价于在关键字全集内做一次二分查找 （假设全部在内存中，用作文件）

推到过程：换底公式$log_a b = log_c b / log_c a$

$O(n) = log_M \frac{n-1}{2} · log_2 M$ 树高*节点内二分查找代价

$=\frac {log_2 \frac{n-1}{2}}{log_2 M} · log_2 M $

$= O(log_2 n)$

查找

查找过程：

顺序查找或者二分查找关键词
关键词是否等于带查找元素：若是则找到
从磁盘中载入关键词对应的子节点
递归查找

节点内对关键词列表采用顺序查找或者二分查找，时间复杂度为O(M)

节点外主要为磁盘IO时间，次数不超过树高$h=log_M (N-1)/2$ 时间复杂度为 O(h)

总的时间复杂度为$O(M·h)$

插入

插入一个元素时，首先在B树中是否存在，如果不存在，即在叶子结点处结束（不会向下添加新的叶子节点，增加一层，保持所有叶子节点都在一层这一性质）
然后在叶子结点中插入该新的元素
- 如果叶子结点空间足够，这里需要向右移动该叶子结点中大于新插入关键字的元素
- 如果空间满了以致没有足够的空间去添加新的元素，则将该结点进行“分裂”，将一半数量的关键字元素分裂到新的其相邻右结点中，中间关键字元素上移到父结点中
- 如果父结点空间满了，也同样需要“分裂”操作，向上传导，如果在根结点插入新元素，空间满了，则进行分裂操作，这样原来的根结点中的中间关键字元素向上移动到新的根结点中，因此导致树的高度增加一层

删除

首先查找B树中需删除的元素,如果该元素在B树中存在，则将该元素在其结点中进行删除，如果删除该元素后，首先判断该元素是否有左右孩子结点，如果有，则上移孩子结点中的第一个或者最后一个元素到父节点中，如果没有，直接删除。

B+树

核心：B+-tree是应文件系统所需而产生的一种B-tree的变形树，B树节点带有关键字以及关键字数据的指针，B+树非叶子节点只包含关键字本身在树高相等情况下，B+树所需要的磁盘IO数小于B树

特点：相比于B树

所有的叶子结点中包含了全部关键字（不包含数据本身，只是包含指向含有这些关键字记录的指针(而B 树的叶子节点并没有包括全部需要查找的信息)
叶子结点本身依关键字的大小自小而大的顺序链接

为什么说B+-tree比B 树更适合实际应用中操作系统的文件索引和数据库索引？

B+-tree的磁盘读写代价更低

B+-tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。

如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多

一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes

一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)
B+-tree的查询效率更加稳定

由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当
B+树方便扫库，对数据库全部遍历/ 支持区间查询

B+树1. 所有关键字都在叶子节点上 2. 叶子节点之间有指针相连接 3. 可以直接从叶子节点扫库 4. 查找区间首尾节点后，通过叶子节点的指针可以区间查询

B树 1. 叶子节点不包括所有的关键字 2. 叶子节点间没有指针 3 需要采用中序遍历的方式才能扫库 4. 区间查询不友好，需要中序遍历

B*树

B*-tree是B+-tree的变体，在B+树的基础上(所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针)，

B 树定义了非叶子结点关键字个数至少为(2/3)M，即块的最低使用率为2/3（代替B+树的1/2）

B* 树中非根和非叶子结点再增加指向兄弟的指针；

B*树分配新结点的概率比B+树要低，空间使用率更高

B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分

数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字

（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之

间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；

B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据

复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父

结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；

LSM树

https://www.cnblogs.com/yanghuahui/p/3483754.html

https://blog.csdn.net/dbanote/article/details/8897599

LSM树的设计思想非常朴素：将对数据的修改增量保持在内存中，达到指定的大小限制后将这些修改操作批量写入磁盘，不过读取的时候稍微麻烦，需要合并磁盘中历史数据和内存中最近修改操作，所以写入性能大大提升，读取时可能需要先看是否命中内存，否则需要访问较多的磁盘文件。极端的说，基于LSM树实现的HBase的写性能比Mysql高了一个数量级，读性能低了一个数量级。